package com.example.learn.hwod;

import java.util.Scanner;

public class _20最左侧冗余覆盖子串 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        String s1 = sc.nextLine();
        String s2 = sc.nextLine();
        int k = sc.nextInt();
        System.out.println(solution(s1,s2,k));

    }

    private static int solution(String s1, String s2, int k) {
        // 在s2中选一个子串，满足:该子串长度为 n1+k
        int n1 = s1.length();
        int n2 = s2.length();
        if (n2 < n1 + k) return -1;

        // 由于字符串s1中都是小写字母，因此每个字母的ASCII码范围是97~122，因此这里初始化128长度数组来作为统计容器
        int[] count = new int[128];

        // 统计s1中所有每个字符出现的次数到count中
        for (int i = 0; i < n1; i++) {
            char c = s1.charAt(i);
            count[c]++;
        }

        // s1字符总数
        int total = n1;

        // 滑动窗口的左边界从0开始，最大maxI；滑动窗口长度len
        int maxI = n2 - n1 - k;
        // s2子串长度
        int len = n1 + k;

        for (int j = 0; j < len; j++) {
            char c = s2.charAt(j);
            if (count[c]-- > 0) {
                total--;
            }
            if (total==0) {
                return 0;
            }
        }

        for (int i = 1; i < maxI; i++) {
            char remove = s2.charAt(i - 1);
            char add = s2.charAt(i - 1 + len);
            if (count[remove]++>=0) {
                total++;
            }
            if (count[add]-- >0) {
                total--;
            }
            if (total==0) {
                return i;
            }

        }

        return -1;
    }
}
